#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x)
	: val(x)
	, left(NULL)
	, right(NULL)
    {
    }
};

TreeNode* pro(map<int, int>& recmap, vector<int>& preorder, vector<int>& inorder,int begin1,int end1,int begin2,int end2)
{
	if((begin1 > end1) || (begin2 > end2)){
		return nullptr;
	}
	if((begin1 == end1) && (begin2 == end2)){
		return new TreeNode(preorder[begin1]);
	}
	int pos=recmap[preorder[begin1]];
	TreeNode *res=new TreeNode(preorder[begin1]);
	int leftlong=pos-begin2+1;
	int rightlong=end2-pos+1;
	TreeNode* left=pro(recmap,preorder,inorder,begin1+1,begin1+leftlong,begin2,pos-1);
	TreeNode* right=pro(recmap,preorder,inorder,begin1+1+leftlong,begin1+leftlong+rightlong,pos+1,end2);
	res->left=left;
	res->right=right;
	return res;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
	if(preorder.size() == 0 || inorder.size() == 0){
		return nullptr;
	}
	map<int,int> recmap;
	for(int i=0;i<inorder.size();++i){
		recmap.insert({inorder[i],i});
	}
	return pro(recmap,preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
}

int main(int argc, char* argv[])
{

    return 0;
}
